1. Field of the Invention
The present invention is related to the field of semiconductor circuits. In particular, the present invention is related to an apparatus for generating random numbers.
2. Description of the Related Art
Random number generation is critical to cryptographic systems. Symmetric ciphers such as data encryption standard (DES) require a randomly selected encryption key. Public-key algorithms like RSA, Diffie-Hellman, and DSA require randomly generated key pairs. Furthermore, the secure sockets layer (SSL) and other cryptographic protocols use random challenges in the authentication process to foil attacks.
Because of the widespread use of random numbers in cryptography, a random number generator must be robust enough so that even if the design of the random number generator is known, the random number generated by the random number generator cannot be predicted. Typically, a random number generator comprises an entropy generator to generate a seed that is then input into a mixing function (e.g., SHA-1, MD5 etc.). However, a large number of random number generators, actually utilize a deterministic process, i.e., a process whose outcome is predictable, to generate an output from an initial seed. This is true in the case of most software embodiments of random number generators. Such random number generators, (also called pseudo random number generators) can be easily compromised, particularly if the seed of the pseudo random number generator can be predicted.
Therefore, a seed generated by a true random number generator is essential for the proper functioning of a pseudo random number generator. A true random number generator (RNG) uses a non-deterministic source, such as, thermal or shot noise associated with a resistor, atmospheric noise, nuclear decay, or some such unpredictable natural process to generate a seed. Some random number generators use a natural process, i.e. the thermal or shot noise present when electrons flow through a resistor, to generate a seed. However, the RNGs of these circuits use analog circuitry that may include at least an operation amplifier and a voltage control oscillator to generate the seed. The use of analog circuits in the design of a RNG makes production of the RNG difficult. For example, due to the high voltage gain needed to amplify the thermal or shot noise, the output of the operation amplifier could become permanently saturated rendering the RNG useless.
Other RNGs use a low frequency clocked circuit to sample the output of a linear feedback shift register (LFSR), wherein the LFSR is driven by a higher frequency free running ring oscillator with a random variation in the frequency to generate random numbers. Due to the use of a low frequency clocked circuit to sample a higher frequency free running oscillator to generate random numbers, a failure of the free running oscillator is difficult to detect (i.e., one needs to monitor the output of the LFSR to determine if a predictable pattern is present). Moreover, RNGs that employ this design usually do not scale well as it is not obvious how to increase the amount of entropy i.e., the random binary bits generated.